package q89_grayCode;

import java.util.ArrayList;
import java.util.List;

public class Solution {
    public static void main(String[] args) {

    }

    /**
     * 一个n位的格雷码存在的性质
     * 1 每个整数都在范围 [0, 2n - 1] 内（含 0 和 2n - 1）
     * 2 第一个整数是 0
     * 3 一个整数在序列中出现 不超过一次
     * 4 每对 相邻 整数的二进制表示 恰好一位不同 ，且
     * 5 第一个 和 最后一个 整数的二进制表示 恰好一位不同
     *
     * 这里使用对称的方式生成格雷码 也就是Gn 和 Gn - 1 之间存在一些关系
     * （只能记忆了）
     * @param n
     * @return
     */
    public List<Integer> grayCode(int n) {
        List<Integer> ret = new ArrayList<Integer>();
        ret.add(0);
        for (int i = 1; i <= n; i++) {
            int m = ret.size();
            for (int j = m - 1; j >= 0; j--) {
                ret.add(ret.get(j) | (1 << (i - 1)));
            }
        }
        return ret;

    }
}
